﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Jarvis.Learners.DecisionTree
{
    class C45DecisionTreeLearner : DecisionTreeLearner
    {
        protected static double GetGainRatioForExamplesWithAttribute(List<Example> node_examples, String attribute)
        {
            double split_info = GetSplitInfoForExamplesByAttribute(node_examples, attribute);

            if (split_info == 0)
                return 0;
            else
            {
                double gain_ratio = GetGainForExamplesWithAttribute(node_examples, attribute) / split_info;
                return gain_ratio;
            }
        }

        protected static double GetSplitInfoForExamplesByAttribute(List<Example> node_examples, String attribute)
        {
            Dictionary<object, List<Example>> subsets = PartitionExamplesByAttribute(node_examples, attribute);

            double split_info = 0;

            double total_count = 0;

            foreach (object key in subsets.Keys)
            {
                total_count = total_count + subsets[key].Count;

                double ratio = ((double) subsets[key].Count) / ((double) node_examples.Count);

                split_info = split_info - (ratio * Math.Log(ratio, 2));
            }

            return (total_count / ((double) node_examples.Count)) * split_info;
        }

        protected static Dictionary<object, List<Example>> PartitionExamplesByAttribute(List<Example> node_examples, String attribute)
        {
            Dictionary<object, List<Example>> subsets = new Dictionary<object, List<Example>>();

            foreach (Example example in node_examples)
            {
                if (example.state.ContainsKey(attribute))
                {
                    object value = example.state[attribute];

                    List<Example> matches = null;

                    if (subsets.ContainsKey(value))
                        matches = subsets[value];
                    else
                    {
                        matches = new List<Example>();
                        subsets[value] = matches;
                    }

                    matches.Add(example);
                }
            }

            return subsets;
        }

        protected static double GetGainForExamplesWithAttribute(List<Example> node_examples, String attribute)
        {
            Dictionary<object, List<Example>> subsets = PartitionExamplesByAttribute(node_examples, attribute);

            double gain = GetInfoForExamples(node_examples);

            double total_count = 0;

            foreach (object key in subsets.Keys)
            {
                List<Example> matches = subsets[key];

                total_count = total_count + matches.Count;

                double info_x = (((double) matches.Count) / ((double) node_examples.Count)) * GetInfoForExamples(matches);

                gain = gain - info_x;
            }

            return (total_count / ((double) node_examples.Count)) * gain;
        }

        protected static double GetInfoForExamples(List<Example> node_examples)
        {
            ArrayList labels = new ArrayList();
            Dictionary<String, double> frequencies = new Dictionary<String, double>();

            foreach (Example example in node_examples)
            {
                String label = example.label;

                if (!labels.Contains(label))
                    labels.Add(label);

                if (frequencies.ContainsKey(label))
                    frequencies[label]++;
                else
                    frequencies[label] = 1;;
            }

            double info = 0;

            foreach (String label in labels)
            {
                double label_prob = (frequencies[label] / node_examples.Count);

                info = info - (label_prob * Math.Log(label_prob, 2));
            }

            return info;
        }

        protected override String GetFeatureForExamples(List<Example> node_examples)
        {
            Dictionary<String, Type> attributes = new Dictionary<String, Type>();

            foreach (Example example in node_examples)
            {
                foreach (String key in example.state.Keys)
                {
                    if (key != null && !attributes.Keys.Contains(key))
                        attributes[key] = example.state[key].GetType();
                }
            }

            double best_ratio = Double.NegativeInfinity;
            String best_feature = null;

            foreach (String key in attributes.Keys)
            {
                Type attribute_type = attributes[key];

                double gain_ratio = Double.NegativeInfinity;

                if (attribute_type.IsAssignableFrom(typeof(Double)))
                {
                    double attribute_gain = Double.NegativeInfinity;
                    double split_value = Double.NegativeInfinity;

                    List<Double> values = new List<Double>();

                    foreach (Example example in node_examples)
                    {
                        if (example.state.ContainsKey(key))
                        {
                            Double value = (Double) example.state[key];

                            if (!values.Contains(value))
                                values.Add(value);
                        }
                    }

                    values.Sort();

                    if (values.Count > 0)
                        values.Remove(values.Last());

                    foreach (Double value in values)
                    {
                        String new_key = key + " >= " + value;

                        foreach (Example example in node_examples)
                        {
                            if (example.state.ContainsKey(key))
                            {
                                if (((Double)example.state[key]) >= value)
                                    example.state[new_key] = "true";
                                else
                                    example.state[new_key] = "false";
                            }
                        }

                        double value_gain = GetGainRatioForExamplesWithAttribute(node_examples, new_key);

                        if (value_gain > attribute_gain)
                        {
                            attribute_gain = value_gain;
                            split_value = value;
                        }
                    }

                    gain_ratio = attribute_gain;

                    foreach (Double value in values)
                    {
                        String new_key = key + " >= " + value;

                        foreach (Example example in node_examples)
                            example.state.Remove(new_key);
                    }

                    foreach (Example example in node_examples)
                        example.splits[key] = split_value;
                }
                else if (attribute_type.IsAssignableFrom(typeof(List<object>)))
                {
                    double attribute_gain = Double.NegativeInfinity;
                    object list_item = null;

                    List<object> values = new List<object>();

                    foreach (Example example in node_examples)
                    {
                        if (example.state.ContainsKey(key))
                        {
                            List<object> node_values = (List<object>) example.state[key];

                            foreach (object value in node_values)
                            {
                                if (!values.Contains(value))
                                    values.Add(value);
                            }
                        }
                    }

                    foreach (object value in values)
                    {
                        String new_key = key + " contains " + value;

                        foreach (Example example in node_examples)
                        {
                            if (example.state.ContainsKey(key))
                            {
                                List<object> list = (List<object>) example.state[key];

                                if (list.Contains(value))
                                    example.state[new_key] = "true";
                                else
                                    example.state[new_key] = "false";
                            }
                        }

                        double value_gain = GetGainRatioForExamplesWithAttribute(node_examples, new_key);

                        if (value_gain > attribute_gain)
                        {
                            attribute_gain = value_gain;

                            list_item = value;
                        }
                    }

                    gain_ratio = attribute_gain;

                    foreach (object value in values)
                    {
                        String new_key = key + " contains " + value;

                        foreach (Example example in node_examples)
                            example.state.Remove(new_key);
                    }

                    foreach (Example example in node_examples)
                        example.subitems[key] = list_item;
                }
                else
                    gain_ratio = GetGainRatioForExamplesWithAttribute(node_examples, key);

                if (best_feature == null)
                    best_feature = key;

                if (gain_ratio > best_ratio)
                {
                    best_ratio = gain_ratio;
                    best_feature = key;
                }
            }

            return best_feature;            
        }
    }
}
